#include <iostream>
#include <time.h>
using namespace std;

//global scope
const int GRADE_COUNT = 5000;

void initializeGradesToRandomValues(int grades[]);
void initializeGradesToOrderedValues(int grades[]);
void displayGrades(int grades[]);
int minGrade (int grades[]);
int maxGrade (int grades[]);
int averageGrade (int grades[]);
int modeGrade (int grades[]);
int medianGrade (int grades[]);
void selectionSort(int grades[]);
void bubbleSort(int grades[]);

void main()
{
	srand(time(NULL));
	int grades[GRADE_COUNT];
	
	//initializeGradesToRandomValues(grades);
	initializeGradesToOrderedValues(grades);
	//displayGrades(grades);

	cout << "min grade = " << minGrade(grades) << endl;
	cout << "max grade = " << maxGrade(grades) << endl;
	cout << "average grade = " << averageGrade(grades) << endl;
	//cout << "mode grade = " << modeGrade(grades) << endl;

	//selectionSort(grades);
	bubbleSort(grades);
	//displayGrades(grades);
}

void initializeGradesToRandomValues(int grades[])
{
	for(int i =0; i < GRADE_COUNT; i++)
	{
		if(rand()%10 == 0)
		{
			grades[i] = rand()%11 + 90;
		}
		else
		{
			grades[i] = rand()%101;
		}
	}
}

void initializeGradesToOrderedValues(int grades[])
{
	for(int i =0; i < GRADE_COUNT; i++)
	{
		grades[i] = i;
	}
	grades[4999] = -1;
}



void displayGrades(int grades[])
{
	for(int i =0; i < GRADE_COUNT; i++)
	{
		cout << grades[i] << endl;
	}
}

int minGrade (int grades[])
{
	int result = grades[0];
	for(int i =0; i < GRADE_COUNT; i++)
	{
		if( grades[i] < result)
		{
			result = grades[i];
		}
	}
	return result;
}

int maxGrade (int grades[])
{
	int result = grades[0];
	for(int i =0; i < GRADE_COUNT; i++)
	{
		if( grades[i] > result)
		{
			result = grades[i];
		}
	}
	return result;
}


int averageGrade (int grades[])
{
	int result = 0;
	for(int i =0; i < GRADE_COUNT; i++)
	{
		result += grades[i];
	}
	return result / GRADE_COUNT;
}

int medianGrade (int grades[])
{
	selectionSort(grades);
	int result = 0;
	if(GRADE_COUNT %2==0)
	{
		result = (grades[GRADE_COUNT/2] + grades[GRADE_COUNT/2-1])/2;
	}
	else
	{
		result = grades[GRADE_COUNT/2];
	}

	return result;
}


int modeGrade (int grades[])
{
	int result = 0;
	int gradefrequencies[101]={0};
	for(int i =0; i < GRADE_COUNT; i++)
	{
		gradefrequencies[grades[i]]++;
	}
	
	for(int j = 0; j < 101;j++)
	{
		if(gradefrequencies[j] > gradefrequencies[result])
		{
			result = j;
		}
	}

	return result;
}

void bubbleSort(int grades[])
{
	int loopCount = 0;
	bool isSorted = false;
	for(int sorted = 0; ((sorted < GRADE_COUNT) && !isSorted); sorted++)
	{
		isSorted = true;
		for(int i = 0; i < GRADE_COUNT - sorted -1; i++)
		{
			loopCount++;
			if(grades[i] > grades[i+1])
			{
				int temp = grades[i];
				grades[i] = grades[i+1];
				grades[i+1] = temp;
				isSorted = false;
			}
		}

	}
	cout << "Loop count = " << loopCount << endl;
}


void selectionSort(int grades[])
{

	for(int sorted = 0; sorted < GRADE_COUNT; sorted++)
	{
		int indexOfBiggest = 0;
		for(int i = 0; i < GRADE_COUNT - sorted;i++)
		{
			if(grades[i] > grades[indexOfBiggest])
			{
				indexOfBiggest = i;
			}
		}
		//we know that indexOfBiggest holds the index
		//of the largest grade in the unsorted part of the list
		//swap (GRADE_COUNT -Sorted -1) with indexOfBiggest

		int temp = grades[indexOfBiggest];
		grades[indexOfBiggest] = grades[GRADE_COUNT - sorted -1];
		grades[GRADE_COUNT - sorted -1] = temp;
	}

}